package sort;

import java.util.Arrays;

//插入排序
//基本思想是:把数组中第一个元素或最后一个元素看作有序集,数组中其它元素看作无序集
//从无序集中依次取出一个元素插入有序集中,最后使整个数组有序,速度和选择排序差不多
//但是如果排序前数组中的元素大体呈现出正序或逆序,插入排序速度就比较慢,可以用希尔排序优化
//希尔排序就是就是优化的插入排序
public class InsertSort {
    public static void main(String[] args) {
        int[] arr = {101,34,145,25,3};
        int index;//定义一个下标,用来指向有序集中的元素
        int insertValue;//定义一个值用来保存插入元素的值
        /*
        * 把数组中第一个元素看作有序集,数组中其它元素看作无序集,从无序集中依次取出一个元素插入有序集中
        * 所以数组下标从1开始,排序的次数为数组元素个数减1
        * */
        for (int i = 1; i < arr.length; i++) {
            index = i-1;//有序集最后一个元素的下标,即为当前插入元素下标的前一个
            insertValue = arr[i];//保存插入元素的值
            /*
            * 插入元素和有序集中的元素进行比较,如果比有序集中的元素小,就把有序集中的元素在数组中的位置先前移动一位
            * 移动完之后,再和下一个有序集中的元素进行比较,index>=0保证数组下标不越界
            * 不满足循环条件时,说明插入元素找到了插入有序集中的位置,插入有序集中
            * */
            while (index>=0 && insertValue<arr[index]) {
                arr[index+1]=arr[index];//把有序集中的元素在数组中的位置先前移动一位
                index--;//有序集下标减1,保证插入元素和有序集中下一个元素进行比较
            }
            //出了循环,说明插入元素找到了插入有序集中的位置,插入有序集中
            arr[index+1] = insertValue;
        }
        System.out.println(Arrays.toString(arr));
    }
}
